#include <bits/stdc++.h>
using namespace std;

/*
1717. 删除子字符串的最大得分
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

删除子字符串 "ab" 并得到 x 分。
比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
删除子字符串"ba" 并得到 y 分。
比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。
请返回对 s 字符串执行上面操作若干次能得到的最大得分。

 

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。
示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20
 

提示：

1 <= s.length <= 105
1 <= x, y <= 104
s 只包含小写英文字母。
*/

// 法一
class Solution {
public:
    int maximumGain(string s, int x, int y) {
        char first = 'a', second = 'b';
        if (y > x)  {
            swap(x, y);
            swap(first, second);
        }

        // 得分
        int sco = 0;
        string tmp;
        // 去掉价值高的子字符串
        for (char ch : s) {
            if (!tmp.empty() && tmp.back() == first && ch == second) {
                tmp.pop_back();
                sco += x;
            } else tmp += ch;
        }
        // 去掉价值低的子字符串
        string finalTmp;
        for (char ch : tmp) {
            if (!finalTmp.empty() && finalTmp.back() == second && ch == first) {
                finalTmp.pop_back();
                sco += y;
            } else finalTmp += ch;
        }
        // 计算处理过后的得分
        return sco;
    }
};

// 法二
class Solution {
public:
    int maximumGain(string s, int x, int y) {
        // 确定优先处理的字符对（ab 或 ba），优先处理分值高的
        char highChar = 'a', lowChar = 'b';
        if (x < y) {
            swap(x, y);           // 确保 x 为较高分值
            swap(highChar, lowChar); // 确保 highChar 为优先处理的字符对的首字符
        }

        int totalScore = 0;         // 最终总得分
        int pendingHighChar = 0;    // 当前未匹配的 highChar 数量
        int pendingLowChar = 0;     // 当前未匹配的 lowChar 数量

        // 遍历字符串中的每个字符
        for (char c : s) {
            if (c == highChar) {
                // 遇到 highChar，增加计数
                pendingHighChar++;
            } else if (c == lowChar) {
                // 遇到 lowChar，检查是否有未匹配的 highChar 可以组成高价值对
                if (pendingHighChar > 0) {
                    totalScore += x;          // 形成高价值对，累计得分
                    pendingHighChar--;        // 消耗一个 highChar
                } else {
                    // 没有可匹配的 highChar，增加 lowChar 计数
                    pendingLowChar++;
                }
            } else {
                // 遇到分隔字符（非 a 或 b），处理当前积累的字符对
                totalScore += min(pendingHighChar, pendingLowChar) * y; // 形成低价值对
                pendingHighChar = 0; // 重置计数
                pendingLowChar = 0;
            }
        }

        // 处理字符串末尾剩余的字符对
        totalScore += min(pendingHighChar, pendingLowChar) * y;

        return totalScore;
    }
};